1. Field of the Invention
This invention relates to an adaptive filter and adapting method thereof and more particularly to an adaptive filter for use for identification of a unknown system of transmission path, space acoustical coupling path and the like and an adapting method thereof.
2. Description of the Related Art
As application of the identification way for identifying an unknown system by an adaptive filter, an echo canceller, noise canceller, howling canceller, adaptive equalizer and the like are well known. The case of an echo canceller which removes an echo leaking from a sending side to a receiving side, e.g., from the four-wire side of a two-wire/four-wire conversion circuit, as an example of related conventional technology, will be described.
The echo canceller generates a dummy echo (echo replica) corresponding to a sending signal by using an adaptive filter having more tap coefficients than an impulse response length of an echo path, in order to suppress an echo leaking from a sending circuit into a receiving circuit in the four-wire side of the two-wire/four-wire conversion circuit.
Typical references for a coefficient correcting algorithm for the adaptive filter for use in the above case, are "Adaptive Noise Cancelling: Principle and Applications", Proceedings of IEEE, No. 12 of 63 volumes, 1975, pp. 1692-1716 (hereinafter referred to as reference 1) and "A Learning Method for System Identification", IEEE Transactions on Automatic Control, No. 3 of 12 volumes, 1967, pp. 282-287 (hereinafter referred to as reference 2) have been known since before.
If there exists a fixed delay between a point on a four-wire circuit in which the echo canceller is inserted and a point of the two-wire/four-wire conversion circuit, the number of taps of the echo canceller needs to be large enough for covering an expected maximum fixed delay amount and response wave form of substantial impulse response. Therefore, if the fixed delay amount is large, the number of taps increases tremendously thereby inducing expansion of hardware size and increase of convergence time due to coefficient mutual interference.
To solve these problems, a method for adaptive control on coefficient allocation by estimating a position of waveform response portion excluding fixed delay portions from impulse response of echo path and then allocating tap coefficients of the adaptive filter around the estimated position has been proposed. ("A Fast Convergence Algorithm for Adaptive FIR Filters with Coarsely Located Taps", Proceeding of International Conference on Acoustics, Speech and Signal Processing 1991, 1991, pp. 1525-528, (hereinafter referred to as "reference 3)).
A point indicated by the reference 3 is to reduce convergence time by estimating a position of the response waveform portion and allocating the taps only near that position. However, according to this method, the estimation of the response waveform position is carried out with the maximum value of the tap coefficient absolute value and only one range in which the tap coefficient allocation is limited is specified. Thus, if there are plural waveform response portions (in case of echo, called multi-echo), the tap allocation limited range must be determined so as to cover all these. If there is a large fixed delay between the respective waveform response portions, an effect of limiting the tap allocation position is reduced so that increase of the convergence time is unavoidable.
To solve this problem, a method in which a fast convergence for the multi-echoes is ensured and the tap coefficients are allocated only at the waveform response portion has been proposed in "A Fast Convergence Algorithm for Sparse-Tap Adaptive FIR Filters for An Unknown Number of Multiple Echoes", 1994, Vol. III, pp. 41-44 (hereinafter referred to as "reference 4")".
FIG. 2 shows a block diagram of a structure of the echo canceller proposed in the "Reference 4". The adaptive filter shown in FIG. 2 contains (N-1) delay elements which delay sending signal inputted from a sending signal input terminal 1, delay element 20.sub.1 --delay element 20.sub.N-1 so that the total number of taps is N including a tap in which delay is 0.
On the other hand, to generate the tap coefficients of the adaptive filter, L coefficient generating circuits 30.sub.1 -30.sub.L are provided. The total tap number of the adaptive filter and coefficient generating circuit number L have a relation of N&gt;L. That is, the adaptive filter shown in FIG. 2 is different from the conventional adaptive filter and provided with a tap coefficient substantially capable of realizing a substantial waveform response portion. Then, by allocating that tap coefficient adaptively at the response waveform, an echo replica is generated.
Therefore, a path switch 7 is provided for switching a connection between the output of the delay element and coefficient generating circuit and further a tap control circuit 50 is provided for controlling this path switch 7. The delay signal of each output of the path switch 7 is supplied to a corresponding coefficient generating circuits 30.sub.1 -30.sub.L and multipliers 40.sub.1 -40.sub.L. The multipliers 40.sub.1 -40.sub.L multiply the tap coefficient values outputted by the coefficient generating circuits 30.sub.1 -30.sub.L and the delay signals outputted by the path switches 7 and then supply the results to an adding circuit 8. The adding circuit 8 adds multiplication results of the multipliers 40.sub.1 -40.sub.L to output the echo replica.
The sending signal inputted to the sending signal input terminal 1 is sent from a sending signal output terminal 2 and then transmitted to the two-wire side by the two-wire/four-wire conversion circuit 3. However, a part of the signal leaks into the receiving side because of impedance unmatching. An echo inputted from a reception signal input terminal 4 is supplied to a subtracter 5. As for the signal at the reception signal input terminal 4, the echo replica outputted from the adder 8 is subtracted by the subtracter 5 and an obtained subtraction result is transmitted to the reception signal output terminal 6. Further, the subtraction result is also supplied to the coefficient generating circuits 30.sub.1 -30.sub.L as error signal for coefficient updating.
Now, assuming the LMS algorithm shown in the "Reference 1" as the coefficient updating algorithm, FIG. 3 shows a block diagram indicating a structure of the coefficient generating circuits 30.sub.i (i=1, 2, . . . , L).
The delay signal and error signal supplied to the coefficient generating circuit 30.sub.i are multiplied by the multiplier 31 and further that result is multiplied by a constant .mu. by a multiplier 32. An output of the multiplier 32 indicates a correction amount of the coefficient and this is added to a coefficient value stored in a storage circuit 34 by an adder 33. Then, an addition result is returned to the storage circuit 34. A value stored in the storage circuit 34 serves as tap coefficient value.
The storage circuit 34 has a function for making a held coefficient value zero if a coefficient clear signal is inputted from a coefficient clear circuit 55.
As evident from the above description, the tap coefficient of the adaptive filter is connected to only part of the delay elements selected by the path switch 7. Hereinafter, a tap to which the tap coefficient is connected is called valid tap and a tap to which the tap coefficient is not connected is called invalid tap. Actual tap coefficient adaptive allocation control is carried out in the following manner.
First, as the initial value, fewer tap coefficients than the actual total tap number are allocated at the same interval. These taps serve as valid tap and taps for which no coefficient is allocated serve as invalid taps.
Next, the tap control circuit 50 will be described with reference to FIG. 2. A control subgroup storage circuit 60 stores subgroup number representing a tap control subgroup composed of a plurality of continuous tap numbers in the order of control. The number of taps belonging to each tap control subgroup is set equally. If the total tap number is 30 and the number of the tap control subgroups is 5, the number of taps belonging to each tap control subgroup is 6.
If the tap control subgroups are expressed by tap numbers belonging to G(i)(i=1, 2, . . . , 5) enclosed by the parentheses { },
G(1)={0, 1, 2, 3, 4, 5} PA1 G(2)={6, 7, 8, 9, 10, 11} PA1 G(3)={12, 13, 14, 15, 16, 17} PA1 G(4)={18, 19, 20, 21, 22, 23} PA1 G(5)={24, 25, 26, 27, 28, 29} PA1 Z(1)=1 PA1 Z(2)=2 PA1 Z(3)=3 PA1 Z(4)=4 PA1 Z(5)=5 PA1 SUM (1)=1.0 PA1 SUM (2)=4.0 PA1 SUM (3)=2.0 PA1 SUM (4)=3.0 PA1 SUM (5)=0.0 PA1 T(i)=SUM (i).multidot.100+10 PA1 T(1)=1.0.multidot.100+10=110 PA1 T(2)=4.0.multidot.100+10=410 PA1 T(3)=2.0.multidot.100+10=210 PA1 T(4)=3.0.multidot.100+10=310 PA1 T(5)=0.0.multidot.100+10=10
In the control subgroup storage circuit 60, as the initial value of the tap control subgroup number, the group numbers are set in the order from the smallest one. That is, if the group numbers held in the control subgroup storage circuit 60 are expressed by Z(n) (n=1, 2, . . . , 5), each group is initially set as follows:
An address pointer for specifying a data reading position of the control subgroup storage circuit 60 is initially set at a head and a head group number is outputted or in the above a first group number, and that group number is outputted. In the above example, Z(1)=1 is outputted.
The invalid tap storage circuit 52 has FIFO (first-in-first-out) structure and stores (N-L) invalid tap numbers. N is total number of taps and L is the number of valid taps.
The tap number calculating circuit 54 calculates total tap numbers excluding the invalid tap numbers stored by the invalid tap storage circuit 52, namely the valid tap numbers, and supplies the calculated tap numbers to the path switch 7 as a tap changeover control signal. The path switch 7 operates to select outputs of the delay elements corresponding to L valid tap numbers sent from the tap number calculating circuit 54 and transmits that output to the coefficient generating circuits 30.
The invalid tap number at the initial state or the initial setting value of the invalid tap storage circuit 52 is selected so that the valid tap numbers are allocated in the order from the smallest value. For example, if it is set that total tap number N=30, valid tap number L=10, invalid tap number N-L=20, the total tap number is 0, 1, 2, . . . , 29. At this time, as the valid tap number, 10 taps are selected from the smallest value as 0, 1, 2, . . . , 9 and the invalid tap number held by the invalid tap storage circuit 52 is initially set to 10, 11, . . . , 29.
After the above initial state setting, coefficient updating for taps (valid taps) selected by the path switch 7 is carried out by the coefficient generating circuits 30.sub.1 -30.sub.L. Each time when coefficient updating is carried out Q times (Q is positive number), coefficient allocation or updating of valid tap position is carried out.
This valid tap position updating is carried out in the following procedure. A minimum coefficient detecting circuit 51 receives a valid tap number outputted by the tap number calculating circuit 54 and a tap coefficient outputted by each coefficient generating circuit and then supplies a valid tap number corresponding to a coefficient whose absolute value is minimum to the invalid tap storage circuit 52 and coefficient clear circuit 55.
The coefficient clear circuit 55 outputs a coefficient clear signal to the coefficient generating circuit corresponding to an inputted tap number to set the coefficient whose absolute value is minimum to zero. Because the invalid tap storage circuit 52 is of first-in-first-out (FIFO) structure, the inputted tap number is stored at the rearmost of queue and a tap number located at the head of the queue is transmitted to a determining circuit 53.
A control tap range calculating circuit 61 receives a tap control subgroup number Z(n) outputted from the control subgroup storage circuit 60 and calculates minimum tap number K.sub.min and maximum tap number K.sub.max of tap numbers belonging to the tap control subgroup or G(Z(n)) and then supplies them to the determining circuit 53.
For example, if Z(n)=1 in the above example, G(Z(n))=G(1)=0, 1, 2, 3, 4, 5, K.sub.max =5, K.sub.min =0 are supplied. If a tap number inputted to the determining circuit 53 is larger than K.sub.max =5 and smaller than K.sub.min =0, the inputted tap number is returned to the invalid tap storage circuit 52. Then, the next tap number in the invalid tap storage circuit 52 is fetched out and inputted to the determining circuit 53. This repeated procedure is continued while the tap number inputted to the determining circuit 53 is 0-5 or until a determining condition that number belongs to a group of Z(n)=1 is satisfied.
If this determining condition is satisfied, the invalid tap number held by the invalid tap storage circuit 52 is established so that a new valid tap is determined.
By the tap position control limited to a tap control subgroup described above, concentrated allocation of the coefficients is enabled.
On the other hand, change of the tap control subgroup is carried out in the following procedure. An absolute value sum calculating circuit 62 receives a valid tap number outputted by the tap number calculating circuit 54 so as to calculate a coefficient absolute value sum of the valid taps belonging to each tap control subgroup. Each absolute value sum is outputted to a counter 63 and a tap control subgroup number in which the absolute value sums are rearranged in the order from the largest one is outputted to a control subgroup updating circuit 59.
The counter 63 is a counter for counting an updating frequency of the tap coefficient, and each time when the coefficient updating frequency reaches a frequency determined by the coefficient absolute value sum of the valid tap of each tap control subgroup supplied from the absolute value sum calculating circuit 62, supplies a control group change signal to the control subgroup storage circuit 60 and counter 58. That is, the larger the absolute value sum of a control subgroup, the longer the time interval in which the counter 63 outputs a control group change signal is.
For example, when selection of all tap control subgroup is ended, that is, the counter 58 outputs a control subgroup order updating signal to the control subgroup updating circuit 59, it is assumed that the coefficient absolute value sum of the valid taps in each tap control subgroup is {1.0, 4.0, 2.0, 3.0, 0.0}. At this time, the coefficient absolute value sum SUM(i) (i=1, 2, . . . , 5) of the valid tap in each tap control subgroup is:
Now, a relation between limit time (expressed by coefficient updating frequency) to be allocated to each tap control subgroup, T(i) (i=1, 2, . . . , 5) and coefficient absolute value sum SUM (i) (i=1,2, . . . , 5) is defined as
In this case, T(i) is:
The tap control subgroup limit order Z(i) (i=1, 2, . . . , 5) is the order of subgroup.
Z (1)=2
Z (2)=4
Z (3)=3
Z (4)=1
Z (5)=5
As evident from the above description, because the tap control range is moved over all taps in succession, even if there are a plurality of substantial waveform response portions such as multiechoes, the tap coefficients can be allocated.
Further, by the tap position control of determining a time taken for changing the limit subgroup from one subgroup to another subgroup, depending on the importance of each subgroup, the more important control subgroup remains the limited subgroup for a longer time, so that the tap coefficients are allocated with precedence over the waveform response portion of the impulse response. As a result, a fast convergence is achieved.
A problem of the conventional art described up to now exists in that because the conventional art is based on tap position control based on growth of the filter coefficient, if the input signal is a signal whose power is not constant like voice signal or the like, that is, there exists no-sound interval or an interval having noise alone, an increase of convergence time may be induced. The reason is as follows. If filter power of a tap belonging to a selected tap control subgroup is very small or the noise component of the signal is large, even if a coefficient of that subgroup is located at a tap position in which the coefficient must grow, stable coefficient growth cannot be expected. As a result, the tap position control is carried out in such a condition in which coefficient growth is difficult, so that the tap position control is not carried out properly.